#include "sorting_algorithm.h"

#include <algorithm>
#include <cassert>
#include <cmath>
#include <string>
#include "log.h"
#include "perf_timer.h"

namespace
{
template<typename T>
constexpr T& GetVectorElement(std::vector<T> &vec, std::ptrdiff_t index) noexcept
{
    assert(index >= 0 && static_cast<std::size_t>(index) < vec.size());
    return vec[static_cast<std::size_t>(index)];
}

template<typename T>
constexpr const T& GetVectorElement(const std::vector<T> &vec, std::ptrdiff_t index) noexcept
{
    assert(index >= 0 && static_cast<std::size_t>(index) < vec.size());
    return vec[static_cast<std::size_t>(index)];
}

void PrintData(const std::vector<int32_t> &data)
{
    std::string result;
    for (const auto &element : data) {
        result += std::to_string(element) + " ";
    }
    SYS_LOG(_DEBUG) << result << '\n';
}
} // namespace

std::vector<int32_t> ISortingAlgorithm::Executor(const std::vector<int32_t> &data)
{
    if (data.empty()) {
        SYS_LOG(_ERROR) << "Input data is empty, skip sort.\n";
        return std::vector<int32_t>();
    }
    SYS_LOG(_INFO) << Descriptor() << '\n';
    data_ = data;
    SYS_LOG(_DEBUG) << "=====> Before Sort: \n";
    PrintData(data_);
    Base::Utils::PerfTimerMs timerMs;
    Sort(data_);
    auto elapsed = timerMs.Elapsed();
    SYS_LOG(_DEBUG) << "=====> After Sort: \n";
#ifdef IS_DEBUG
    PrintData(data_);
#endif // IS_DEBUG
    SYS_LOG(_INFO) << "Sort elapsed time: " << elapsed << " ms\n";
    return data_;
}

void BubbleSort::Sort(std::vector<int32_t> &data)
{
    auto dataSize = std::ssize(data);
    for (std::ptrdiff_t i = 0; i < dataSize - 1; ++i) {
        bool swapped = false;
        for (std::ptrdiff_t j = 0; j < dataSize - 1 - i; ++j) {
            if (GetVectorElement(data, j) <= GetVectorElement(data, j + 1)) {
                continue;
            }
            SYS_LOG(_DEBUG) << "Swapping elements: data[j]=" <<
                GetVectorElement(data, j) << " and data[j + 1]=" << GetVectorElement(data, j + 1) << '\n';
            std::swap(GetVectorElement(data, j), GetVectorElement(data, j + 1));
            swapped = true;
        }
        SYS_LOG(_DEBUG) << "=====> the " << i + 1 << "th cycle, result: \n";
#ifdef IS_DEBUG
        PrintData(data);
#endif // IS_DEBUG
        if (!swapped) {
            SYS_LOG(_DEBUG) << "No elements swapped, array is sorted.\n";
            break;
        }
    }
}

void InsertionSort::Sort(std::vector<int32_t> &data)
{
    auto dataSize = std::ssize(data);
    for (std::ptrdiff_t i = 0; i < dataSize; ++i) {
        auto key = GetVectorElement(data, i);
        auto j = i - 1;
        while (j >= 0 && GetVectorElement(data, j) > key) {
            SYS_LOG(_DEBUG) << "Moving element: data[" << j << "]=" << GetVectorElement(data, j) <<
                " to index:" << j + 1 << '\n';
            GetVectorElement(data, j + 1) = GetVectorElement(data, j);
            --j;
        }
        GetVectorElement(data, j + 1) = key;
        SYS_LOG(_DEBUG) << "=====> the " << i + 1 << "th insertion, result: \n";
#ifdef IS_DEBUG
        PrintData(data);
#endif // IS_DEBUG
    }
}

void QuickSort::Sort(std::vector<int32_t> &data)
{
    QuickSortRecursive(data, 0, std::ssize(data) - 1);
}

std::ptrdiff_t QuickSort::Partition(std::vector<int32_t> &data, std::ptrdiff_t low, std::ptrdiff_t high)
{
    // 分区函数：选择最左元素为基准，进行分区
    auto pivot = GetVectorElement(data, low);
    auto i = low;
    auto j = high;
    while (i < j) {
        // 先从右向左找第一个小于pivot的元素
        while (i < j && GetVectorElement(data, j) >= pivot) {
            --j;
        }
        // 再从左向右找第一个大于pivot的元素
        while (i < j && GetVectorElement(data, i) <= pivot) {
            ++i;
        }
        if (i < j) {
            std::swap(GetVectorElement(data, i), GetVectorElement(data, j));
        }
    }
    // 将基准值放到最终位置
    std::swap(GetVectorElement(data, low), GetVectorElement(data, i));
    SYS_LOG(_DEBUG) << "pivot=" << pivot << " low=" << low << " high=" << high << " pivotIndex=" << i <<'\n';

    return i;
}

void QuickSort::QuickSortRecursive(std::vector<int32_t> &data, std::ptrdiff_t low, std::ptrdiff_t high)
{
    if (low < high) {
        // 获取基准位置
        auto pivotIndex = Partition(data, low, high);
        // 递归排序左半部分
        QuickSortRecursive(data, low, pivotIndex - 1);
        // 递归排序右半部分
        QuickSortRecursive(data, pivotIndex + 1, high);
    }
}

void MergeSort::Sort(std::vector<int32_t> &data)
{
    MergeSortRecursive(data, 0, std::ssize(data) - 1);
}

void MergeSort::Merge(std::vector<int32_t> &data, std::ptrdiff_t left, std::ptrdiff_t mid, std::ptrdiff_t right)
{
#ifdef IS_DEBUG
    static int32_t mergeCount = 1;
    SYS_LOG(_DEBUG) << "=====> the " << mergeCount++ << "th merge: " <<
    "[left=" << left << ", data=" << GetVectorElement(data, left) << "], " <<
    "[mid=" << mid << ", data=" << GetVectorElement(data, mid) << "], " <<
    "[right=" << right << ", data=" << GetVectorElement(data, right) << "]" << '\n';
#endif // IS_DEBUG
    std::vector<int32_t> temp(static_cast<size_t>(right - left + 1));
    auto i = left;          // 左子数组起始索引
    auto j = mid + 1;       // 右子数组起始索引
    std::ptrdiff_t k = 0;   // 临时数组索引

    while (i <= mid && j <= right) {
        SYS_LOG(_DEBUG) << "[left=" << i << ", data=" << GetVectorElement(data, i) << "], " <<
        "[right=" << j << ", data=" << GetVectorElement(data, j) << "]" << '\n';
        if (GetVectorElement(data, i) <= GetVectorElement(data, j)) {
            SYS_LOG(_DEBUG) << "Taking left element to subarray: " << GetVectorElement(data, i) << '\n';
            GetVectorElement(temp, k++) = GetVectorElement(data, i++);
        } else {
            SYS_LOG(_DEBUG) << "Taking right element to subarray: " << GetVectorElement(data, j) << '\n';
            GetVectorElement(temp, k++) = GetVectorElement(data, j++);
        }
    }

    while (i <= mid) {
        SYS_LOG(_DEBUG) << "Taking remaining left element to subarray: " <<
        "[left=" << i << ", data=" << GetVectorElement(data, i) << "]" << '\n';
        GetVectorElement(temp, k++) = GetVectorElement(data, i++);
    }

    while (j <= right) {
        SYS_LOG(_DEBUG) << "Taking remaining right element to subarray: " << GetVectorElement(data, i) <<
        "[right=" << j << ", data=" << GetVectorElement(data, j) << "]" << '\n';
        GetVectorElement(temp, k++) = GetVectorElement(data, j++);
    }

    for (std::ptrdiff_t p = 0; p < std::ssize(temp); ++p) {
        GetVectorElement(data, (left + p)) = GetVectorElement(temp, p);
    }
#ifdef IS_DEBUG
        PrintData(data);
#endif // IS_DEBUG
}

void MergeSort::MergeSortRecursive(std::vector<int32_t> &data, std::ptrdiff_t left, std::ptrdiff_t right)
{
    // 基线条件
    if (left >= right) {
        return;
    }

    auto mid = left + (right - left) / 2; // 防止溢出
    MergeSortRecursive(data, left, mid);
    MergeSortRecursive(data, mid + 1, right);
    Merge(data, left, mid, right);  // 合并
}

void HeapifySort::Sort(std::vector<int32_t> &data)
{
    auto dataSize = std::ssize(data);
    // 构建最大堆
    for (std::ptrdiff_t i = dataSize / 2 - 1; i >= 0; --i) {
        Heapify(data, dataSize, i);
    }
    // 一个个从堆中取出元素
    for (std::ptrdiff_t i = dataSize - 1; i > 0; --i) {
        std::swap(GetVectorElement(data, 0), GetVectorElement(data, i)); // 将当前根节点与最后一个节点交换
        Heapify(data, i, 0); // 重新堆化根节点
    }
}

void HeapifySort::Heapify(std::vector<int32_t> &data, std::ptrdiff_t n, std::ptrdiff_t i)
{
    auto largest = i;         // 初始化最大值为根节点
    auto left = 2 * i + 1;    // 左子节点索引
    auto right = 2 * i + 2;   // 右子节点索引
    SYS_LOG(_DEBUG) << "Heapifying heapSize=" << n << " ,index=" << i <<
        ", left=" << left << ", right=" << right << '\n';

    // 如果左子节点比根节点大
    if (left < n && GetVectorElement(data, left) > GetVectorElement(data, largest)) {
        SYS_LOG(_DEBUG) << "left=largest=" << GetVectorElement(data, left) << '\n';
        largest = left;
    }

    // 如果右子节点比当前最大值大
    if (right < n && GetVectorElement(data, right) > GetVectorElement(data, largest)) {
        SYS_LOG(_DEBUG) << "right=largest=" << GetVectorElement(data, left) << '\n';
        largest = right;
    }

    // 如果最大值不是根，则需要交换并递归调整被破坏的子堆
    if (largest != i) {
        std::swap(GetVectorElement(data, i), GetVectorElement(data, largest));
#ifdef IS_DEBUG
        PrintData(data);
#endif // IS_DEBUG
        Heapify(data, n, largest);
    }
}